#include "MyMergeSort.h"
#include<vector>
using namespace std;


//合并
void merge(vector<int>& arr,int l,int mid,int r){
    int n = r-l+1;
    vector<int> temp(n);//辅助空间
    int p = 0;
    
    int i = l,j = mid+1;
    while(i<=mid && j<=r){
      if(arr[i]<=arr[j]){
          temp[p++] = arr[i++];
      }else{
          temp[p++] = arr[j++];
      }
    }

    while(i<=mid){
        temp[p++] = arr[i++];
    }

    while(j<=r){
        temp[p++] = arr[j++];
    }

    for(p=0;p<n;++p) arr[p+l] = temp[p];//拷贝回原数组

}

//分治思想
void sort(vector<int>& arr,int l,int r){
    if(l==r) return;//就一个数,已经有序了

    int mid = (l+r)/2;
    sort(arr,l,mid);//左边排序去吧
    sort(arr,mid+1,r);//右边排序去吧
    merge(arr,l,mid,r);//左右都已经排好,做个合并老子这个区间的任务就完成啦
}

void MergeSort(vector<int>& arr){
    if(arr.empty()) return;

    int l = 0,r = arr.size()-1;
    sort(arr,l,r);
}
